#include <bits/stdc++.h>
#ifndef DEBUG
#define debug
#endif
using namespace std;
using i64 = int64_t;

const int inf = INT_MAX / 2;
int main() {
  cin.tie(0)->sync_with_stdio(0);
  int T;
  cin >> T;
  for (int cas = 1; cas <= T; cas ++) {
    int n;
    cin >> n;
    vector<int> s(n + 1);
    for (int i = 1; i <= n; i ++) cin >> s[i];
    vector<vector<int>> dp(n + 1, vector<int>(n + 1));
    for (int l = n; l >= 1; l --) {
      for (int r = l; r <= n; r ++) {
        if (all_of(s.begin() + l, s.begin() + r + 1, [&](char c) { return c == s[l]; })) {
          dp[l][r] = 1;
          continue;
        }
        
        dp[l][r] = inf;
        for (int k = l; k < r; k ++) {
          dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r]);
        }
        if (s[l] == s[r]) {
          for (int k = l; k < r; k ++) {
            if (s[k] == s[l]) {
              dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r - 1]);
            }
          }
        }
      }
    }
    cout << "Case " << cas << ": " << dp[1][n] << endl;
  }
}